package cn.edu.xjtu.data_structure.experiment.ex_3.refer;

import java.util.Random;

/**
 * Implements a treap.
 * Note that all "matching" is based on the compareTo method.
 */
public class TreapBinary<T extends Comparable<? super T>> {

    private TreapNode<T> root;
    private TreapNode<T> nullNode;

    /**
     * Construct the treap.
     */
    public TreapBinary() {
        nullNode = new TreapNode<>(null);
        nullNode.left = nullNode.right = nullNode;
        nullNode.priority = Integer.MAX_VALUE;
        root = nullNode;
    }

    /**
     * Insert into the tree. Does nothing if x is already present.
     * @param x the item to insert.
     */
    public void insert(T x) {
        root = insert(x, root);
    }

    /**
     * Remove from the tree. Does nothing if x is not found.
     * @param x the item to remove.
     */
    public void remove(T x) {
        root = remove(x, root);
    }

    /**
     * Find the smallest item in the tree.
     * @return the smallest item, or throw UnderflowException if empty.
     */
    public T findMin() {
        TreapNode<T> ptr = root;
        while(ptr.left != nullNode) {
            ptr = ptr.left;
        }
        return ptr.element;
    }

    /**
     * Find the largest item in the tree.
     * @return the largest item, or throw UnderflowException if empty.
     */
    public T findMax() {
        TreapNode<T> ptr = root;
        while(ptr.right != nullNode) {
            ptr = ptr.right;
        }
        return ptr.element;
    }

    /**
     * Find an item in the tree.
     * @param x the item to search for.
     * @return true if x is found.
     */
    public boolean contains(T x) {
        TreapNode<T> current = root;
        nullNode.element = x;
        while(true) {
            int compareResult = x.compareTo(current.element);
            if(compareResult < 0) {
                current = current.left;
            } else if(compareResult > 0) {
                current = current.right;
            } else {
                return current != nullNode;
            }
        }
    }

    /**
     * Make the tree logically empty.
     */
    public void makeEmpty() {
        root = nullNode;
    }

    /**
     * Test if the tree is logically empty.
     * @return true if empty, false otherwise.
     */
    public boolean isEmpty() {
        return root == nullNode;
    }

    /**
     * Print the tree contents in sorted order.
     */
    public void printTree() {
        if(isEmpty()) {
            System.out.println("Empty tree");
        } else {
            printTree(root);
        }
    }

    /**
     * Internal method to insert into a subtree.
     * @param x the item to insert.
     * @param t the node that roots the subtree.
     * @return the new root of the subtree.
     */
    private TreapNode<T> insert(T x, TreapNode<T> t) {
        if(t == nullNode) {
            return new TreapNode<>(x, nullNode, nullNode);
        }
        int compareResult = x.compareTo(t.element);
        if(compareResult < 0) {
            t.left = insert(x, t.left);
            if(t.left.priority < t.priority) {
                t = rotateWithLeftChild(t);
            }
        } else if(compareResult > 0) {
            t.right = insert(x, t.right);
            if(t.right.priority < t.priority) {
                t = rotateWithRightChild(t);
            }
        }
        // Otherwise, it's a duplicate; do nothing
        return t;
    }

    /**
     * Internal method to remove from a subtree.
     * @param x the item to remove.
     * @param t the node that roots the subtree.
     * @return the new root of the subtree.
     */
    private TreapNode<T> remove(T x, TreapNode<T> t) {
        if(t != nullNode) {
            int compareResult = x.compareTo(t.element);
            if(compareResult < 0) {
                t.left = remove(x, t.left);
            } else if(compareResult > 0) {
                t.right = remove(x, t.right);
            } else {
                // Match found
                if(t.left.priority < t.right.priority) {
                    t = rotateWithLeftChild(t);
                } else {
                    t = rotateWithRightChild(t);
                }
                if(t != nullNode) {  // Continue on down
                    t = remove(x, t);
                } else {
                    t.left = nullNode;  // At a leaf
                }
            }
        }
        return t;
    }

    /**
     * Internal method to print a subtree in sorted order.
     * @param t the node that roots the tree.
     */
    private void printTree(TreapNode<T> t) {
        if(t != t.left) {
            printTree(t.left);
            System.out.println(t.element.toString());
            printTree(t.right);
        }
    }

    /**
     * Rotate binary tree node with left child.
     */
    private TreapNode<T> rotateWithLeftChild(TreapNode<T> k2) {
        TreapNode<T> k1 = k2.left;
        k2.left = k1.right;
        k1.right = k2;
        return k1;
    }

    /**
     * Rotate binary tree node with right child.
     */
    private TreapNode<T> rotateWithRightChild(TreapNode<T> k1) {
        TreapNode<T> k2 = k1.right;
        k1.right = k2.left;
        k2.left = k1;
        return k2;
    }

    private static class TreapNode<T> {
        TreapNode(T theElement) {
            this(theElement, null, null);
        }

        TreapNode(T theElement, TreapNode<T> lt, TreapNode<T> rt) {
            element  = theElement;
            left     = lt;
            right    = rt;
            priority = randomObj.nextInt(100000);
        }

        // Friendly data; accessible by other package routines
        T element;      // The data in the node
        TreapNode<T> left;         // Left child
        TreapNode<T> right;        // Right child
        int priority;     // Priority

        private static Random randomObj = new Random();
    }
        public static void main(String[] args) {
            TreapBinary<Integer> t = new TreapBinary<>();
            final int NUMS = 40000;
            final int GAP  = 307;
            System.out.println("Checking... (no bad output means success)");
            for(int i = GAP; i != 0; i = (i+GAP) % NUMS) {
                t.insert(i);
            }
            System.out.println("Insert completely");
            for(int i = 1; i < NUMS; i+= 2) {
                t.remove(i);
            }
            System.out.println("Remove completely");
            if(NUMS < 40) {
                t.printTree();
            }
            if(t.findMin() != 2 || t.findMax() != NUMS-2) {
                System.out.println("FindMin or FindMax error!");
            }
            for(int i = 2; i < NUMS; i+=2) {
                if(!t.contains(i)) {
                    System.out.println("Error: find fails for " + i);
                }
            }
            for(int i = 1; i < NUMS; i+=2) {
                if(t.contains(i)) {
                    System.out.println("Error: Found deleted item " + i);
                }
            }
        }


}
